Network switches, routers, and various other network devices typically include a plurality of queues for storing packets received in a network environment. The packets can be maintained in the queues in a received order and scheduled for forwarding to other network devices or removal for other network processes. Each packet may have an associated priority, and each queue may have packets with different priorities. A scheduler may schedule packets for dequeuing based on their relative priorities. For example, the scheduler may examine the head-of-line packet in each of the queues and schedule the packet with the highest priority.
One problem with such a queuing system is head-of-line blocking. Head-of-line blocking may occur when a low priority packet present at the head of one of the queues blocks higher-priority packets behind it in the same queue. When this occurs, higher priority packets at the head of other queues will be scheduled before the low priority packet and thus removed from the other queues. The high priority packets removed from the other queues may be replaced with other high priority packets. In this case, the low priority packet may not be scheduled for a long time because the other higher priority packets from other queues are being serviced and the lower priority is bypassed for service. Thus, the low priority packet may block the high priority packets behind it. These high priority packets may have been scheduled if it were not for the low priority packet at the head of the queue. The blocking of high priority packets is undesirable in many applications.
Several techniques have been developed for managing head-of-line blocking. For example, one technique includes assigning a virtual queue to each packet priority and servicing the packets from the highest priority virtual queue first. Lower priority virtual queues are serviced after all of the packets in the higher priority queues have been serviced. Thus, a lower priority packet is prevented from blocking a higher priority packet. One problem with this technique is that a single stream may have packets belonging to multiple priorities. Therefore, a higher priority packet may be serviced out of order from an earlier-received low priority packet in the same stream because they use different queues. Therefore, packet re-ordering may result. Packet re-ordering is undesirable in many higher layer applications.
Accordingly, there exists a need for methods, systems, and computer program products for scheduling prioritized packets in multiple queues in an efficient manner and that prevents head-of-line blocking and that services packets belonging to the same stream in a first-in first-out (FIFO) manner.